import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    //柠檬水找零
    public static boolean lemonadeChange(int[] bills) {
        int fiveCount = 0, tenCount = 0;
        for(int i = 0; i < bills.length; i++){
            if(bills[i] == 5){
                fiveCount++;
            }else if(bills[i] == 10){
                if(fiveCount >= 1){
                    fiveCount--;
                    tenCount++;
                }else{
                    return false;
                }
            }else{
                if(tenCount >= 1 && fiveCount >= 1){
                    tenCount--;
                    fiveCount--;
                }else if(fiveCount >= 3){
                    fiveCount -= 3;
                }else{
                    return false;
                }
            }
        }
        return true;
    }

    //将数组和减半的最小操作次数
    public static int halveArray(int[] nums) {
        PriorityQueue<Double> priorityQueue = new PriorityQueue<>(( o1, o2)->{
            return o2.compareTo(o1);
        });
        double sum = 0.0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
            priorityQueue.add((double)nums[i]);
        }
        int count = 0;
        double newSum = sum;
        while (newSum > sum / 2){
            count++;
            double tmp = priorityQueue.poll() / 2;
            newSum -= tmp;
            priorityQueue.add(tmp);
        }
        return count;
    }
    //最大数
    public String largestNumber(int[] nums1) {
        Integer[] nums = Arrays.stream(nums1).boxed().toArray(Integer[]::new);
        Arrays.sort(nums, (o1, o2) ->{
            String s1 = o1.toString() + o2.toString();
            String s2 = o2.toString() + o1.toString();
            return s2.compareTo(s1);
        });
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < nums.length; i++) {
            ret.append(nums[i]);
        }
        if(ret.charAt(0) == '0'){
            return "0";
        }else {
            return ret.toString();
        }
    }
    //摆动序列
    public int wiggleMaxLength(int[] nums) {
        int left = 0, right = 0;
        int ret = 0;
        for(int i = 0; i < nums.length - 1; i++){
            right = nums[i+1] - nums[i];
            if(right == 0) continue;
            else if(left * right <= 0){
                ret++;
                left = right;
            }
        }
        ret++;//最后一个节点
        return ret;
    }

    public static void main(String[] args) {
        int[] bills = {5,5,5,10,20};
      //  lemonadeChange(bills);
        int[] nums = {5,19,8,1};
        halveArray(nums);
    }
}